home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_src.lha / LEDA-3.1c-source / src / graph / _g_generate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-17  |  9.5 KB  |  460 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _g_generate.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/array.h>
  17. #include <LEDA/graph.h>
  18. #include <LEDA/ugraph.h>
  19. #include <ctype.h>
  20.  
  21. // some graph generators
  22.  
  23. void complete_graph(graph& G, int n)
  24. { node v,w;
  25.   G.clear();
  26.   while (n--) G.new_node();
  27.   forall_nodes(v,G)
  28.      forall_nodes(w,G) 
  29.         G.new_edge(v,w);
  30. }
  31.  
  32. void complete_ugraph(ugraph& G, int n)
  33. { int i,j;
  34.   node* V = new node[n];
  35.   G.clear();
  36.   for(i=0;i<n;i++) V[i] = G.new_node();
  37.   for(i=0;i<n;i++) 
  38.     for(j=i+1;j<n;j++) 
  39.        G.new_edge(V[i],V[j]);
  40. }
  41.  
  42.  
  43. void grid_graph(graph& G, int n) 
  44. { node_array<double> xcoord; 
  45.   node_array<double> ycoord;
  46.   grid_graph(G,xcoord,ycoord,n);
  47.  }
  48.  
  49. void grid_graph(graph& G, node_array<double>& xcoord, 
  50.                           node_array<double>& ycoord, int n) 
  51. {
  52.   array2<node>  A(n,n);
  53.   node v;
  54.   int N = n*n;
  55.   int x;
  56.   int y;
  57.  
  58.   double d = 1.0/(n+1);
  59.  
  60.   G.clear();
  61.  
  62.   xcoord.init(G,N,0);
  63.   ycoord.init(G,N,0);
  64.  
  65.   for(y=0; y<n; y++)
  66.     for(x=0; x<n; x++)
  67.       { A(x,y) = v = G.new_node();
  68.         xcoord[v] = (x+1)*d;
  69.         ycoord[v] = (y+1)*d;
  70.        }
  71.  
  72.   for(x=0; x<n; x++)
  73.     for(y=0; y<n; y++)
  74.        { if (x < n-1) G.new_edge(A(x,y),A(x+1,y));
  75.          if (y < n-1) G.new_edge(A(x,y),A(x,y+1));
  76.         }
  77. }
  78.  
  79.  
  80. void complete_bigraph(graph& G, int n1, int n2, list<node>& A, list<node>& B)
  81. { node v,w;
  82.  
  83.   for(int a=0; a < n1; a++)  A.append(G.new_node());
  84.   for(int b=0; b < n2; b++)  B.append(G.new_node());
  85.  
  86.   forall(v,A) 
  87.   {  forall(w,B) 
  88.        G.new_edge(v,w);
  89.    }
  90.  }
  91.  
  92. void user_graph(graph& G)
  93. { int  n = read_int("|V| = ");
  94.   int  i,j;
  95.  
  96.   node* V = new node[n];
  97.   for(j=0; j<n; j++) V[j] = G.new_node();
  98.  
  99.   for(j=0; j<n; j++) 
  100.   { list<int> il;
  101.     bool ok = false;
  102.     while (!ok)
  103.     { ok = true;
  104.       cout << "edges from [" << j << "] to: ";
  105.       il.read();
  106.       forall(i,il) 
  107.         if (i < 0 || i >= n) 
  108.         { ok=false;
  109.           cout << "illegal node " << i << "\n";
  110.          }
  111.      }
  112.     forall(i,il) G.new_edge(V[j],V[i]);
  113.   }
  114.   G.print();
  115.   if (Yes("save graph ? ")) G.write(read_string("file: "));
  116. }
  117.  
  118.  
  119.  
  120. void test_graph(graph& G)
  121. { 
  122.   G.clear();
  123.   char c;
  124.  
  125.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  126.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  127.  
  128.   switch (c) {
  129.  
  130.    case 'f' : { G.read(read_string("file: "));
  131.                 break;
  132.                }
  133.  
  134.    case 'u' : { user_graph(G);
  135.                 break;
  136.                }
  137.  
  138.    case 'c' : { complete_graph(G,read_int("|V| = "));
  139.                 break;
  140.                }
  141.  
  142.    case 'r' : { int n = read_int("|V| = ");
  143.                 int m = read_int("|E| = ");
  144.                 random_graph(G,n,m);
  145.                 break;
  146.                }
  147.  
  148.    case 'p' : { random_planar_graph(G,read_int("|V| = "));
  149.                 break;
  150.                }
  151.    }//switch
  152.  
  153. }
  154.  
  155. void test_ugraph(ugraph& G)
  156. { 
  157.   G.clear();
  158.   char c;
  159.  
  160.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  161.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  162.  
  163.   int  i;
  164.   node v;
  165.   
  166.   switch (c) {
  167.  
  168.   case 'f' : { G.read(read_string("file: "));
  169.                break;
  170.               }
  171.  
  172.    case 'u' : { int  n = read_int("|V| = ");
  173.                 int  j = 0;
  174.                 node* V = new node[n];
  175.                 loop(i,0,n-1) V[i] = G.new_node();
  176.                 forall_nodes(v,G)
  177.                   { list<int> il;
  178.                     cout << "edges from " << j++ << " to: ";
  179.                     il.read();
  180.                     forall(i,il) 
  181.                       if (i >= 0 && i < n) G.new_edge(v,V[i]);
  182.                       else cerr << "illegal node " << i << " (ignored)\n";
  183.                    }
  184.                 G.print();
  185.                 if (Yes("save graph ? ")) G.write(read_string("file: "));
  186.                 break;
  187.                }
  188.  
  189.    case 'c' : { int n = read_int("|V| = ");
  190.                 complete_graph(G,n);
  191.                 break;
  192.                }
  193.  
  194.    case 'r' : { int n = read_int("|V| = ");
  195.                 int m = read_int("|E| = ");
  196.                 random_graph(G,n,m);
  197.                 break;
  198.                }
  199.  
  200.    }//switch
  201.  
  202. }
  203.  
  204.  
  205.  
  206.  
  207.  
  208. void test_bigraph(graph& G, list<node>& A, list<node>& B)
  209. {
  210.   int  a,b,n1,n2;
  211.   char c;
  212.  
  213.   do c = read_char("bipartite graph: f(ile) r(andom) c(omplete) u(ser): ");
  214.   while (c!='f' && c!='r' && c!='c' && c!='u');   
  215.  
  216.   A.clear();
  217.   B.clear();
  218.   G.clear();
  219.  
  220.   if (c!='f') 
  221.    { n1 = read_int("|A| = ");
  222.      n2 = read_int("|B| = ");
  223.     }
  224.   
  225.   
  226.   switch (c) {
  227.  
  228.   case 'f' : { G.read(read_string("file: "));
  229.                node v;
  230.                forall_nodes(v,G) 
  231.                if (G.outdeg(v) > 0) A.append(v);
  232.                else B.append(v);
  233.  
  234.                break;
  235.               }
  236.  
  237.    case 'u' : { node* AV = new node[n1+1];
  238.                 node* BV = new node[n2+1];
  239.  
  240.                 loop(a,1,n1)  A.append(AV[a] = G.new_node());
  241.                 loop(b,1,n2)  B.append(BV[b] = G.new_node());
  242.  
  243.                 loop(a,1,n1)
  244.                   { list<int> il;
  245.                     cout << "edges from " << a << " to: ";
  246.                     il.read();
  247.                     forall(b,il) if (b<=n2) G.new_edge(AV[a],BV[b]);
  248.                                  else break;
  249.                     if (b>n2) break;
  250.                    }
  251.                 break;
  252.                }
  253.  
  254.    case 'c' : complete_bigraph(G,n1,n2,A,B);
  255.               break;
  256.  
  257.    case 'r' : { int m = read_int("|E| = ");
  258.                 random_bigraph(G,n1,n2,m,A,B);
  259.                 break;
  260.                }
  261.  
  262.        } // switch
  263.  
  264. }
  265.  
  266.  
  267.  
  268. void cmdline_graph(graph& G, int argc, char** argv)
  269. { 
  270.   // construct graph from cmdline arguments
  271.  
  272.   if (argc == 1)           // no arguments 
  273.      { test_graph(G);
  274.        return;
  275.       }
  276.   else 
  277.      if (argc == 2)       // one argument
  278.         { if (isdigit(argv[1][0])) 
  279.              { cout << "complete graph |V| = " << argv[1];
  280.                newline;
  281.                newline;
  282.                complete_graph(G,atoi(argv[1]));
  283.               }
  284.           else 
  285.              { cout << "reading graph from file " << argv[1];
  286.                newline;
  287.                newline;
  288.                G.read(argv[1]);
  289.               }
  290.           return;
  291.          }
  292.      else
  293.         if (argc == 3 && isdigit(argv[1][0]) && isdigit(argv[1][0])) 
  294.            { cout << "random graph |V| = " << argv[1] << "  |E| = " << argv[2];
  295.              newline;
  296.              newline;
  297.              random_graph(G,atoi(argv[1]),atoi(argv[2]));
  298.              return;
  299.             }
  300.  
  301.   error_handler(1,"cmdline_graph: illegal arguments");
  302. }
  303.  
  304.  
  305.  
  306.  
  307. //------------------------------------------------------------------------------
  308. // triangulated planar graph
  309. //------------------------------------------------------------------------------
  310.  
  311.  
  312. #include <LEDA/d_array.h>
  313.  
  314.  
  315. struct triang_point {
  316.  
  317. double x,y;
  318.  
  319. LEDA_MEMORY(triang_point)
  320.  
  321. triang_point(double a=0, double b = 0) { x = a; y = b; }
  322.  
  323. bool operator==(const triang_point& p) { return x==p.x && y==p.y; }
  324.  
  325. friend int compare(const triang_point& p, const triang_point& q)
  326. { int c = compare(p.x,q.x);
  327.   if (c==0) c = compare(p.y,q.y);
  328.   return c;
  329.  }
  330.  
  331. friend void Print(const triang_point&, ostream&) {}
  332. friend void Read(triang_point&, istream&) {}
  333.  
  334.  
  335. friend bool right_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  336. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) > 0; }
  337.  
  338. friend bool left_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  339. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) < 0; }
  340.  
  341. };
  342.  
  343.  
  344.  
  345. #if !defined(__TEMPLATE_FUNCTIONS__)
  346. LEDA_TYPE_PARAMETER(triang_point)
  347. #endif
  348.  
  349.  
  350. void triangulated_planar_graph(graph& G, node_array<double>& xcoord,
  351.                                          node_array<double>& ycoord, int n)
  352. { 
  353.  
  354.   list<triang_point> L;
  355.   list<triang_point> CH;
  356.   list_item last;
  357.   triang_point p,q;
  358.  
  359.   for(int i = 0; i < n; i++)
  360.  
  361.   L.append(triang_point(rrandom(),rrandom()));
  362.  
  363.   L.sort();  // sort triang_points lexicographically
  364.  
  365.  
  366.   // eliminate multiple triang_points
  367.  
  368.   list_item it;
  369.   forall_items(it,L)
  370.   { list_item it1 = L.succ(it);
  371.     while (it1 != nil && L[it1] == L[it])
  372.     { L.del(it1);
  373.       it1 = L.succ(it);
  374.      }
  375.    }
  376.  
  377.   n = L.length();
  378.  
  379.   d_array<triang_point,node> V(nil);
  380.  
  381.   xcoord.init(G,n,0);
  382.   ycoord.init(G,n,0);
  383.  
  384.   forall(p,L) 
  385.   { node v = G.new_node();
  386.     xcoord[v] = p.x;
  387.     ycoord[v] = p.y;
  388.     V[p] = v;
  389.    }
  390.  
  391.  
  392.   // initialize convex hull with first two points
  393.  
  394.   p = L.pop();
  395.   CH.append(p);
  396.  
  397.   while (L.head() == p) L.pop();
  398.   q = L.pop();
  399.   last = CH.append(q);
  400.  
  401.   G.new_edge(V[p],V[q]);
  402.  
  403.  
  404.   // scan remaining points
  405.  
  406.   forall(p,L)
  407.   {
  408.     node v = V[p];
  409.  
  410.     G.new_edge(v,V[CH[last]]);
  411.  
  412.     // compute upper tangent (p,up)
  413.  
  414.     list_item up = last;
  415.     list_item it = CH.cyclic_succ(up);
  416.  
  417.     while (left_turn(CH[it],CH[up],p))
  418.     { up = it;
  419.       it = CH.cyclic_succ(up);
  420.       G.new_edge(v,V[CH[up]]);
  421.      }
  422.  
  423.  
  424.     // compute lower tangent (p,low)
  425.  
  426.     list_item low = last;
  427.     it = CH.cyclic_pred(low);
  428.  
  429.     while (right_turn(CH[it],CH[low],p))
  430.     { low = it;
  431.       it = CH.cyclic_pred(low);
  432.       G.new_edge(v,V[CH[low]]);
  433.      }
  434.  
  435.  
  436.     // remove all points between up and low
  437.  
  438.     if (up != low)
  439.     { it = CH.cyclic_succ(low);
  440.  
  441.       while (it != up)
  442.       { CH.del(it);
  443.         it = CH.cyclic_succ(low);
  444.        }
  445.      }
  446.  
  447.     // insert new point
  448.  
  449.     last = CH.insert(p,low);
  450.  
  451.    }
  452.  
  453. }
  454.  
  455. void triangulated_planar_graph(graph& G, int m)
  456. { node_array<double> xcoord;
  457.   node_array<double> ycoord;
  458.   triangulated_planar_graph(G,xcoord,ycoord,m);
  459.  }
  460.